This invention relates to a method and apparatus for expanding or decoding binary image data coded in a two-dimensional compressional code, such as a MR code, to original image data, and will be suitable, for example, for expanding the data which is transmitted by a high speed facsimile apparatus or read from an optical disk, a magnetic disk, or the like, and which has been coded in the code described above.
The MR (Modified READ) code is a two-dimensional compressional code for binary image data that is recommended by CCITT Recommendation T.4 for GIII facsimile apparatuses. More specifically, the MR coding is a line-by-line coding method in which the position of each changing picture element on the current or coding line is coded with respect to the position of a corresponding reference element situated on either the coding line or the reference line which lies immediately above the coding line. After the coding line has been coded it becomes the reference line for the next coding line. Since an example of an MR coding apparatus is described in detail in Japanese Patent Laid-Open No. 256274/1985, only the outline of the MR coding will be described herein to an extent necessary for understanding extension processing.
FIGS. 1A and 1B show the summary of the rule for MR coding and symbols in these drawings have the following meaning.
a.sub.0 : The reference or starting changing element on the coding line. At the start of the coding line a.sub.0 is set on an imaginary white changing element situated just before the first element on the line. During the coding of the coding line, the position of a.sub.0 is defined by the previous coding mode. PA0 a.sub.1 : The next changing element to the right of a.sub.0 on the coding line. PA0 a.sub.2 : The next changing element to the right of a.sub.1 on the coding line. PA0 b.sub.1 : The first changing element on the reference line to the right of a.sub.0 and of opposite color to a.sub.0. PA0 b.sub.2 : The next changing element to the right of b.sub.1 on the reference line.
A changing element is defined as a picture element whose color (i.e. black or white) is different from that of the previous picture element along the same scan line. In FIG. 1B, the expression "a.sub.1 b.sub.1 =0", "a.sub.1 b.sub.1 =1", or the like, represents that the distance between a.sub.1 and b.sub.1 is 0 picture element (pixel) or 1 picture element, or the like. Furthermore, the expression M(a.sub.0 a.sub.1) and M(a.sub.1 a.sub.2) represent the MH (Modified Huffman) codes corresponding to the number of pixels (or run length) from a.sub.0 to a.sub.1 and from a.sub.1 to a.sub.2, respectively, and its coding rule, too, is described in detail in the afore-mentioned CCITT Recommendation T.4.
The MR coding is broadly classified into three modes. A pass mode identifies a mode where b.sub.2 lies to the left of a.sub.1 and the code in this mode is determined uniquely irrespective of the distance. A horizontal mode identifies a mode where b.sub.2 is at the same position as, or to the right of, a.sub.1 and the distance between a.sub.1 and b.sub.1 is at least four pixels. The code in this mode represents the distances between a.sub.0 and a.sub.1 and between a.sub.1 and a.sub.2. A vertical mode identifies a mode other than the two modes described above, where b.sub.2 is at the same position as, or to the right of, a.sub.1 and moreover, the distance between a.sub.1 and b.sub.1 is at most three pixels. The code in this mode represents the relative position of a.sub.1 to b.sub.1. When one coding is completed, a.sub.0 is shifted to the position of b.sub.2 in the pass mode, to the position of a.sub.2 in the horizontal mode and to the position of a.sub.1 in the vertical mode in order to carry out the next coding. FIG. 1C shows a flowchart of this coding procedure.
FIG. 2 shows a basic flowchart of the expanding procedure of the MR code. In the drawing, a reference line changing point search mode is a mode which indicates whether an element changing point (i.e. point at which the picture element color changes) from white to black or a changing point from black to white is to be searched for when the reference line is searched for an element changing point while outputting dot data after detection of a V code or P code. An EOL code is a code which represents the end of a line which is added immediately after a series of codes corresponding to the image data of an entire line.
In a facsimile apparatus utilizing a telephone line or a slow leased line, expanding has been effected through executing sequentially numerous steps obtained by fractionating the flowchart of FIG. 2 by means of a program-controlled microprocessor. In order to reduce a long processing time necessary for sequential processing by the software described above, Japanese Patent Laid-Open No. 194465/1983 proposes in its FIG. 4 an apparatus comprising the combination of a program-controlled processing circuit with an exclusive processing circuit for determining the position of the picture element changing point. In this apparatus, the program-controlled processing circuit extracts the data on the reference line by a predetermined length and writes it into a shift register in the exclusive processing circuit. When the program-controlled processing circuit detects the existence of a picture element changing point, the reference line data in the shift register is shifted out bit by bit and the existence of the picture element change is inspected at its output end. The shift length till detection of the picture element change is then sent as the position data of the picture element changing point to the program-controlled processing apparatus. The program-controlled processing apparatus generates dot data of the output line by use of the picture element changing point position data and the output of a decoding circuit.
In the facsimile apparatus utilizing the telephone line or the slow leased line, the transmission rate of the line is in the order of from 1/10 to 1/100 of the processing speed inside the apparatus. Accordingly, even if the MR code is expanded sequentially to the dot data by program control, the expanding processing speed does not become a problem. However, in the case of high speed facsimile using a high speed line or an image file system using an optical disk or a magnetic disk, the expanding processing speed must be improved drastically. Though the system which sequentially expands the code to the dot data by program control provides the advantage that the necessary amount of hardware is small, a drastic improvement in its processing speed can never be expected.
The apparatus shown in FIG. 4 of afore-mentioned Japanese Patent Laid-Open No. 194465/1983 improves the processing speed to some extent. However, processing other than the decision of the element changing point is sequentially carried out by program control and moreover, its exclusive processing circuit detects the picture element changing point on the reference line bit-serially so that its processing speed must yet be improved drastically.